

<HTML>

<HEAD>

<LINK rel="stylesheet" href="../exer.css">

</HEAD>

<BODY>

<H1>

Data Structures, Algorithms, & Applications in C++<BR>

Chapter 12, Exercise 1<BR>

<BR>

</H1>





<dl compact>

<dt> (a)

<dd>

The in-degrees of the vertices of graph (a) are [0,3,1,1,1].<br>

The in-degrees of the vertices of graph (b) are [2,1,2,0,2].<br>

The in-degrees of the vertices of graph (c) are [1,1,1,3,1].<br>



<br>

<dt> (b)

<dd>

The out-degrees of the vertices of graph (a) are [2,0,2,1,1].<br>

The out-degrees of the vertices of graph (b) are [0,2,1,3,1].<br>

The out-degrees of the vertices of graph (c) are [2,2,1,0,2].<br>



<br>

<dt> (c)

<dd>

There are no vertices adjacent from vertex 2 in graph (a).<br>

Vertices 1 and 3 are adjacent from vertex 2 in graph (b).<br>

Vertices 3 and 5 are adjacent from vertex 2 in graph (c).<br>



<br>

<dt> (d)

<dd>

There are no vertices adjacent to vertex 1 in graph (a).<br>

Vertices 2 and 4 are adjacent to vertex 1 in graph (b).<br>

Vertex 5 is the only vertex adjacent to vertex 1 in graph (c).<br>



<br>

<dt> (e)

<dd>

(3,5) and (3,2) are the only edges incident from vertex 3 in graph (a).<br>

(3,5) is the only edge incident from vertex 3 in graph (b).<br>

(3,4) is the only edge incident from vertex 3 in graph (c).<br>



<br>

<dt> (f)

<dd>

(1,4) is the only edge incident to vertex 4 in graph (a).<br>

Graph (b) has no edges incident to vertex 4.<br>

(1,4), (5,4), and (3,4) are only edges incident to vertex 4 in graph (c).<br>



<br>

<dt> (g)

<dd>

Graph (a) has no directed cycles.<br>

2,3,5,2 is the only directed cycle in graph (b). Its length is 3.<br>

1,2,5,1 is the only directed cycle in graph (c). Its length is 3.<br>



</FONT>

</BODY>

</HTML>

